import java.util.ArrayList;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2022-11-11
 * Time: 23:48
 */

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    int index2=-1;
    int index1=-1;//记录错误的下标
    int num1=0;
    int num2=0;//记录错误的值
    public int count=0;//记录遍历时的下标
    public List<Integer> list=new ArrayList<>();
    //中序遍历
    public void inOrder(TreeNode root){
        if(root==null){
            return ;
        }
        inOrder(root.left);
        list.add(root.val);
        inOrder(root.right);
    }

    //中序遍历并修改
    public void modify(TreeNode root){
        if(root==null){
            return ;
        }
        modify(root.left);
        if(count==index1){
            root.val=num2;
        }else if(count==index2){
            root.val=num1;
        }
        count++;
        modify(root.right);
    }
    public void recoverTree(TreeNode root) {
        //先中序遍历
        inOrder(root);
        //寻找错误的位置的下标
        for(int i=0;i<this.list.size()-1;i++){
            int left=list.get(i);
            int right=list.get(i+1);
            if(left>right){
                if(index1==-1){
                    index1=i;
                    num1=left;
                }else{
                    //已经找到第一个了
                    index2=i+1;
                    num2=right;
                }
            }
        }
        //有可能遍历时只能找出一个,那么另一个的下标就是第一个+1
        if(index2==-1){
            index2=index1+1;
            num2=list.get(index2);
        }
        //修改
        modify(root);
    }
}
